package org.chnxi.study.datastructrues.josephulist;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Iterator;

/**
 * 单向循环列表
 */
public class CircleSingleLinkedList<T> {

    //创建一个first节点
    private Node first = null;

    private Node last = null;

    public void add(T t){
        Node<T> node = new Node<>(t);

        if(first == null){
            first = node;
            node.next = node;
            last = node;
        }else{
            last.next = node;
            node.next = first;
            last = node;
        }
    }

    public void printList(){
        //链表是否为空
        if(first == null){
            return;
        }

        Node tmp = first;
        while(true){
            System.out.println(tmp.t);
            if(tmp.next == first){
                break;
            }
            tmp = tmp.next;
        }
    }

    /**
     * 约瑟夫出圈
     * @param startIdx 从第几位开始，最小值0
     * @param step 步长，最小值1
     * @param count 总出圈数量
     */
    public void josephu(int startIdx , int step , int count){
        if(startIdx < 0 || step < 1 || startIdx > count){
            return;
        }

        Node helper = last;
        Node start = first;
        for (int i =0;i<startIdx;i++){
            start = start.next;
            helper = helper.next;
        }

        int out = 0;

        while(true){
            //说明只有一个元素存在
            if(helper == start){
                break;
            }
            for (int j=0;j<step-1;j++){
                start = start.next;
                helper = helper.next;
            }
            System.out.println("出圈："+start.getT());

            start = start.next;
            helper.next = start;

            out++;
            if(out >= count){
                break;
            }
        }
        System.out.println("剩余元素：");
        while(true){
            System.out.println("剩余元素："+start.getT());
            if(start.equals(helper)){
                break;
            }
            start = start.next;
        }

    }

}

@Data
@NoArgsConstructor
@AllArgsConstructor
class Node<T>{

    T t;
    Node<T> next;

    Node(T t){
        this.t = t;
    }

}